/*!
 Temelia - Algorithms samples.

 Copyright (C) 2008 Ceata (http://ceata.org/proiecte/temelia).

 @author Dascalu Laurentiu

 This program is free software; you can redistribute it and
 modify it under the terms of the GNU General Public License
 as published by the Free Software Foundation; either version 3
 of the License, or (at your option) any later version.

 This program is distributed in the hope that it will be useful,
 but WITHOUT ANY WARRANTY; without even the implied warranty of
 MERCHANTABILITY or FITNESS FOR A PARTICULAR PURPOSE.  See the
 GNU General Public License for more details.

 You should have received a copy of the GNU General Public License
 along with this program; if not, write to the Free Software
 Foundation, Inc., 51 Franklin Street, Fifth Floor, Boston, MA  02110-1301, USA.
 */

#include <string.h>
#include "include/samples.h"
#include <temelia/algorithms.h>
#include <temelia/vector.h>
#include <temelia/linked_list.h>
#include <temelia/iterator.h>
#include <temelia/queue.h>

static void my_print_function(void *key, void *context)
{
	PRINT("%d ", *(int *) key);
}

static void my_2power_function(void *key, void *context)
{
	int aux = *(int *) key;
	*(int *) key = aux * aux;
}

static int my_is_prime_number(void *key, void *context)
{
	int p = *(int *) key;
	int i = 0;

	if (p <= 1)
		return 0;
	if (p == 2)
		return 1;

	if (p % 2 == 0)
		return 0;

	for (i = 3; i * i <= p; i += 2)
		if (p % i == 0)
			return 0;

	return 1;
}

static void *vector_my_key_at(void *data, int index)
{
	return vector_get_key_at((vector_t) data, index);
}

static void my_then_function(void *data, void *context)
{
	queue_push_back((queue_t) context, data);
}

static void my_free_function(void *data, void *context)
{
	// This function receives as second parameter
	// a pointer to the free function, standard free in this case
	void (*free_function)(void *key) = (void(*)(void *)) context;

	free_function(data);
}

/*!
 * Demonstrates how useful can be the map function; it's native in functional
 * languages like Haskell and Scheme.
 */
static void sample1()
{
	/*!
	 * The simplest indexable collection is array.
	 */
	int **my_collection = NULL, n = 25;

	PRINT("\n\n Sample 1 started \n\n");

	my_collection = int_array_new(n, 100);

	PRINT("\n Collection before :\n");
	map(my_collection, n, my_key_at, my_print_function, NULL);

	map(my_collection, n, my_key_at, my_2power_function, NULL);

	PRINT("\n Collection after :\n");
	map(my_collection, n, my_key_at, my_print_function, NULL);

	// Free my_collection pointers via iterating
	map(my_collection, n, my_key_at, my_free_function, free);

	// Free the base collection pointer
	free(my_collection);
	my_collection = NULL;

	PRINT("\n\n Sample 1 ended \n\n");
}

/*!
 * Demonstrates binary_search.
 */
static void sample2()
{
	int **my_collection = NULL, i, n = 25, *x = malloc(sizeof(int));

	PRINT("\n\n Sample 2 started \n\n");

	my_collection = int_array_new(n, n);

	for (i = 0; i < n; i++)
		my_collection[i][0] = i;

	*x = n * n;
	PRINT("%d %d %d\n", binary_search(my_collection, n, NULL, my_key_at,
					int_compare, NULL), binary_search(my_collection, n, x, my_key_at,
					int_compare, NULL), binary_search(my_collection, n, my_collection[n / 2],
					my_key_at, int_compare, NULL));

	for (i = 0; i < n; i++)
		PRINT("%d\n", binary_search(my_collection, n, my_collection[i],
						my_key_at, int_compare, NULL));
	int_array_delete(my_collection, n);
	my_collection = NULL;
	free(x);
	x = NULL;

	PRINT("\n\n Sample 2 ended \n\n");
}

/*!
 * Stress test for binary search.
 */
static void sample3()
{
	int **my_collection = NULL, i, n = 100000;

	PRINT("\n\n Sample 3 started \n\n");

	my_collection = int_array_new(n, 2);

	for (i = 0; i < n; i++)
		my_collection[i][0] = i;

	for (i = 0; i < n; i++)
	{
		if (binary_search(my_collection, n, my_collection[i], my_key_at,
				int_compare, NULL) != i)
		{
			PRINT("Sample 3 failed, check this line %d !!", __LINE__);
		}
	}

	int_array_delete(my_collection, n);
	my_collection = NULL;

	PRINT("\n\n Sample 3 ended \n\n");

}

void my_handler(void *key, void *context)
{
	// Print the key
	int_handler(key, context);

	// Free the pointer associated
	int_delete(key, context);
}

/*!
 * Filters the prime numbers in a vector from the non-prime ones by building
 * up a queue with each sort
 */
static void sample4()
{
	int n = 1000, i, *p;
	vector_t v = NULL;
	queue_t q1 = NULL, q2 = NULL;

	PRINT("\n\n Sample 4 started \n\n");

	v = vector_new(n);
	q1 = queue_new(n);
	q2 = queue_new(n);

	PRINT("\n\n Initial vector \n\n");
	for (i = 0; i < n; i++)
	{
		p = (int *) malloc(sizeof(int));
		*p = i + 2;
		vector_push_back(v, (void *) p);
	}

	vector_iterate(v, int_handler, NULL);

	printf("Doing filter....\n");
	filter((void *) v, n, vector_my_key_at, my_is_prime_number,
			my_then_function, my_then_function, NULL, (void *) q1, (void *) q2);

	PRINT("\n Prime numbers are in the first list \n");
	queue_iterate(q1, my_handler, NULL, 1);
	PRINT("\n Nonprime numbers are in the second list \n");
	queue_iterate(q2, my_handler, NULL, 1);

	vector_delete(v);
	v = NULL;
	queue_delete(q1);
	q1 = NULL;
	queue_delete(q2);
	q2 = NULL;

	PRINT("\n\n Sample 4 ended \n\n");
}

static void *list_head(void *data)
{
	// The head of the list is the key stored in this node
	return linked_list_iterator_get_key(data);
}

static void *list_tail(void *data)
{
	// Return the next cell in the linked list
	return linked_list_iterator_get_next(data);
}

static void *yield_sum(void *x, void *y, void *context)
{
	int *sum, _x, _y;
	sum = malloc(sizeof(int));

	if (x)
		_x = *(int *) x;
	else
		_x = 0;

	if (y)
		_y = *(int *) y;
	else
		_y = 0;

	*sum = _x + _y;
	printf("Obtained %d from [%d %d]\n", *sum, _x, _y);
	return sum;
}

static void int_free(void *key, void *context)
{
	free(key);
}

static void sample5()
{
	int n = 5, i, *acc_fl, *acc_fr, *sum_fl, *sum_fr, *key;
	linked_list_t list = NULL;

	PRINT("\n\n Sample 5 started \n\n");

	list = linked_list_new();

	for (i = 0; i < n; i++)
	{
		key = (int *) malloc(sizeof(int));
		*key = i + 2;
		linked_list_push_back(list, (void *) key);
	}

	acc_fl = (int *) malloc(sizeof(int));
	acc_fr = (int *) malloc(sizeof(int));
	*acc_fl = *acc_fr = 100;

	sum_fl = fold_left(NULL, linked_list_get_begin(list), list_head, list_tail,
			yield_sum, int_free, NULL);
	PRINT("The sum with fold left: %d\n\n", *sum_fl);
	free(sum_fl);

	sum_fl = fold_left(acc_fl, linked_list_get_begin(list), list_head, list_tail,
			yield_sum, int_free, NULL);
	PRINT("The sum with fold left and initial number: %d\n\n\n", *sum_fl);
	free(sum_fl);


	sum_fr = fold_right(NULL, linked_list_get_begin(list), list_head, list_tail,
			yield_sum, int_free, NULL);
	PRINT("The sum with fold right: %d\n\n", *sum_fr);
	free(sum_fr);

	sum_fr = fold_right(acc_fr, linked_list_get_begin(list), list_head, list_tail,
			yield_sum, int_free, NULL);
	PRINT("The sum with fold right and initial number: %d\n", *sum_fr);
	free(sum_fr);

	linked_list_iterate(list, int_delete, NULL, 1);
	linked_list_delete(list);

	PRINT("\n\n Sample 5 ended \n\n");
}

static void *string_array_head(void *data)
{
	return ((char **)data)[0];
}

static void *string_array_tail(void *data)
{
	return ((char **)data) + 1;
}

static void string_free(void *key, void *context)
{
	free(key);
}

static void *yield_concat(void *x, void *y, void *context)
{
	char *ret;
	int size = 1;

	if (x) size += strlen(x);
	if (y) size += strlen(y);

	ret = (char *) calloc(size, sizeof(char));

	if (x) strcat(ret, x);
	if (y) strcat(ret, y);

	return ret;
}

static void sample6()
{
	char **list_str, *acc;

	PRINT("\n\n Sample 6 started \n\n");

	list_str = (char **) malloc(5 * sizeof(char *));
	list_str[0] = "| salutare |";
	list_str[1] = "| voinici |";
	list_str[2] = "| ai |";
	list_str[3] = "| Cetei |";
	list_str[4] = NULL;

	acc = fold_left(NULL, list_str, string_array_head, string_array_tail,
		yield_concat, string_free, NULL);
	PRINT("Concatenation with fold left:\n %s\n", acc);
	string_free(acc, NULL);

	acc = fold_left(strdup("| oho |"), list_str, string_array_head, string_array_tail,
		yield_concat, string_free, NULL);
	PRINT("Concatenation with fold left and initial string:\n %s\n", acc);
	string_free(acc, NULL);

	acc = fold_right(NULL, list_str, string_array_head, string_array_tail,
		yield_concat, string_free, NULL);
	PRINT("Concatenation with fold right:\n %s\n", acc);
	string_free(acc, NULL);

	acc = fold_right(strdup("| oho |"), list_str, string_array_head, string_array_tail,
		yield_concat, string_free, NULL);
	PRINT("Concatenation with fold right and initial string:\n %s\n", acc);
	string_free(acc, NULL);

	free(list_str);

	PRINT("\n\n Sample 6 ended \n\n");
}

void run_algorithms_samples()
{
	sample1();
	sample2();
	sample3();
	sample4();
	sample5();
	sample6();
}
